package review;

import java.util.Arrays;

import resource.SortTestHelper;

public class MergeSort {
	public static void merge(Comparable[] arry,int l,int mid,int r){
		//为了保证挪动后的有序性，拷贝了相同的数组
		Comparable[] tmp=Arrays.copyOfRange(arry,l,r+1);
		int i=l,j=mid+1;
		for(int k=l;k<=r;k++){
			if(i>mid){
				arry[k]=tmp[j-l];
				j++;
			}else if(j>r){
				arry[k]=tmp[i-l];
				i++;
			}else if(tmp[i-l].compareTo(tmp[j-l])<0){
				arry[k]=tmp[i-l];
				i++;
			}else if(tmp[i-l].compareTo(tmp[j-l])>=0){
				arry[k]=tmp[j-l];
				j++;
			}
		}
		
	}
	public static void sort(Comparable[] arry,int l,int r){
		if(l>=r){
			return;
		}
		int mid=(r+l)/2;
		sort(arry,l,mid);
		sort(arry,mid+1,r);
		merge(arry,l,mid,r);
	}
	public static Comparable[] sort(Comparable[] arry){
		int n=arry.length;
		sort(arry,0,n-1);
		return arry;
	}
public static void main(String[] args) {
	Integer[] arry=new  SortTestHelper().generateRandomArray(20, 0, 20);
	System.out.println(Arrays.toString(arry));
	Object[] array=sort(arry);
	System.out.println(Arrays.toString(arry));
	//Object[] result=sort(arry);
}
}
